import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] array ={1,4,3,2,4,6,7,8,76,5,4};
        new HeapSort().heapsort(array);
        System.out.println(Arrays.toString(array));
    }
    void heapsort(int[] array){
        buildMaxheap(array);
        //循环取出堆顶元素
        for(int i= array.length-1;i>=1;i--){
            swap(array, i, 0);
            maxHeapify(array, i, 0);
        }
    }

    void buildMaxheap(int[] array){
        //为了减少计算量，array.length/2-1 是最小开始构建堆的元素位置
        //当然从最后一个元素开始构建也可以，但是效率极低，做了一半无效计算
        for(int i=array.length/2-1;i>=0;i--){
            maxHeapify(array, array.length, i);
        }
    }

    // n是必要的，用于排序弹出元素时，控制长度
    void maxHeapify(int[] array,int n,int i){
        int left=2*i+1;
        int right=2*(i+1);
        int max=i;
        if(left<n && array[left]>array[max]){
            max=left;
        }
        if(right<n && array[right]>array[max]){
            max=right;
        }
        if(max!=i){
            //递归
            swap(array,i,max);
            maxHeapify(array, n, max);
        }
    }

    void swap(int[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
}
